【算法题】素数之积

共计 1036 个字符，预计需要花费 3 分钟才能阅读完成。

题目

RSA加密算法在网络安全世界中无处不在，它利用了极大整数因数分解的困难度，数据越大，安全系数越高，给定一个32位正整数， 请对其进行因数分解，找出是哪两个素数的乘积。

描述:

输入：一个正整数num（0 < num <= 2147483647）
输出：如果成功找到，以单个空格分割，从小到大输出两个素数，分解失败，请输出-1 -1

示例1

输入 15
输出 3 5
说明 因数分解后，找到两个素数3和5，使得3*5=15，按从小到大排列后，输出3 5

示例2

输入 27
输出 -1 -1
说明 通过因数分解，找不到任何素数，使得他们的乘积为27，输出-1 -1

知识点补充

1. 如果一个数字不是素数 那它除了1和他本身一定还有别的约数
2. 如果一个数的约数在其开平方的右边 则必然会存在一个约数在其开平方的左边
3. 判断一个数是否为质数 只需要观察在其2 到 开平方数中间是否含有约数即可
   比如说 判断16是否为质数 我们去找16的约数时 判断它的范围 只需要找到
   16的开平方数就可以了 而不必一直找到<16 或者<= 16/2

JAVA解法

import java.util.Scanner;

/**
 * @since 2022-04-11
 */
public class ProductOfPrime {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int a = -1;
        int b = -1;
        // 计算输入数字的平方根，原因如上
        double sqrt = Math.sqrt(num);
        for (int i = 2; i <= sqrt; i++) {
            // 判断是否为素数
            if (!isPrime(i)) {
                continue;
            }
            // 判断能否整除
            if (num % i != 0) {
                continue;
            }
            // 判断另一个乘数是否为素数
            if (!isPrime(num / i)) {
                continue;
            }
            // 结果赋值
            a = i;
            b = num / i;
        }

        System.out.println(a + " " + b);
    }

    /**
     * 判断是否是素数
     *
     * @param arg 入参
     * @return bool
     */
    public static boolean isPrime(int arg) {
        if (arg <= 1) {
            return false;
        }
        // 计算输入数字的平方根，原因如上
        double sqrt = Math.sqrt(arg);
        for (int j = 2; j <= sqrt; j++) {
            if (arg % j == 0) {
                return false;
            }
        }
        return true;
    }

}